import java.util.ArrayList;
import java.util.Collections.*;
import java.util.Collection;
import java.util.*;

/** Represents a node in a graph.
 * @author Dan King, Ian Helmke
 * @param <LI> The type of information embedded within the links contained
 *             within this node.
 * @param <NI> The type of information embedded within this node.
 */
class Node<NI, LI> implements INode<NI, LI> {
  private ArrayList<ILink<LI, NI>> neighbors;
  private final NI info;

  Node(NI info) {
    this(new ArrayList<ILink<LI, NI>>(), info);
  }

  /** The Constructor.
   * @param name The name of this node.
   * @param neighbors An arraylist of neighbors around this node.
   */
  Node(ArrayList<ILink<LI, NI>> neighbors, NI info) {
    this.neighbors = neighbors;
    this.info = info;
  }

  /** Gets an interable of the links of this node.
      @return An iterable of all the links originating at this node.
  */
  public Iterable<ILink<LI, NI>> getLinks() {
    return neighbors;
  }

  /** Gets underlying information about this node. This could be a string
      representing the name of the node, an integer representing it's number,
      or a class with compound data.
      @return The information embedded within this node.
  */
  public NI getInfo() {
    return this.info;
  }

  /** Clears all the the neighbor links this node has */
  public void clearNeighbors() {
    this.neighbors = new ArrayList<ILink<LI, NI>>();
  }

  /** Adds the given link to this node.
      @param newLink The link to be added.
  */
  public void addLink(ILink<LI, NI> newLink) {
    this.neighbors.add(newLink);
  }

  /**
   * Gets the link at the given index
   * @param int the index
   * @return ILink<LI, NI> the link at the given index
   **/
  public ILink<LI, NI>getLink(int index) {
    return this.neighbors.get(index);
  }

  /**
   * Determines if this node is connected to that node.
   * @param Node the destination node
   * @return boolean true if this node is connected to that node
   **/
  public boolean isConnectedTo(INode<NI,LI> that) {
    return isConnectedTo(that, new ArrayList<INode<NI, LI>>());
  }

  /*
  /**
   * Determines if this node is connected to that node.  <code>seen</code> is
   * the list of Nodes which have already been seen
   * @param Node the destination node
   * @return boolean true if this node is connected to that node
   ** /
  public boolean isConnectedToAcc(INode<NI,LI> that, ArrayList<INode<NI, LI>> seen) {
    if(seen.contains(that))
      return false;
    else if(that.equals(this))
      return true;
    else {
      Iterator<INode<NI, LI>> neigh
    }
  }
  */

  /**
   * Determines if this node is connected to that node.
   * @param Node the destination node
   * @param seen the nodes that have already been visited
   * @return boolean true if this node is connected to that node
   **/
  public boolean isConnectedTo(INode<NI, LI> that, ArrayList<INode<NI, LI>> seen) {
    if(this.getInfo().equals(that.getInfo()))
      return true;
    else {
      Iterator<ILink<LI, NI>> linkIterator = this.neighbors.iterator();
      boolean hasLink = false;
      seen.add(this);

      while(!hasLink && linkIterator.hasNext()) {
        INode<NI, LI> temp = linkIterator.next().getDestination();
        if(!seen.contains(temp))
          hasLink = temp.isConnectedTo(that, seen);
      }
      return hasLink;
    }
  }

  /**
   * Determines equality of two nodes based on their node information
   * @param Object the object to compare equality to
   **/
  public boolean equals(Object that) {
    return that instanceof INode
      &&   ((INode)that).getInfo().equals(this.getInfo());
  }

  /**
   * provides a useful string to print to the user
   * @return String a descriptive string representing this object
   **/
  public String toString() {
    return this.info.toString();
  }
}
